package com.advanced;

import com.lx.algorithm.structure.Node;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-29 19:03:35
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-29     张李鑫                     1.0         1.0 Version
 */
public class SortList {
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode node = head;
        ListNode[] arr = new ListNode[getNodeSize(node)];
        node = head;
        int i = 0;
        while (node != null) {
            arr[i++] = node;
            node = node.next;
        }
        process(arr, 0, arr.length - 1);
        for (int i1 = 0; i1 < arr.length - 1; i1++) {
            arr[i1].next = arr[i1 + 1];
        }
        arr[arr.length - 1].next = null;
        return arr[0];
    }

    public static void process(ListNode[] listNodes, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        process(listNodes, left, mid);
        process(listNodes, mid + 1, right);
        mergeArr(listNodes, left, mid, right);
    }


    public static void mergeArr(ListNode[] listNodes, int left, int mid, int right) {
        ListNode[] list = new ListNode[right - left + 1];
        int listIndex = 0;
        int p = left;
        int p2 = mid + 1;
        while (p <= mid && p2 <= right) {
            list[listIndex++] = listNodes[p].val < listNodes[p2].val ? listNodes[p++] : listNodes[p2++];
        }
        while (p <= mid) {
            list[listIndex++] = listNodes[p++];
        }

        while (p2 <= right) {
            list[listIndex++] = listNodes[p2++];
        }
        for (int i = 0; i < list.length; i++) {
            listNodes[left++] = list[i];
        }
    }

    public static int getNodeSize(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }

    public static void main(String[] args) {
        //[-1,5,3,4,0]
        ListNode listNode = new ListNode(5, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(1)))));

        //基于数组的排序
//        ListNode listNode1 = sortList(listNode);


        ListNode listNode1 = sortListNode(listNode);

        System.out.println(123);

    }


    public static ListNode sortListNode(ListNode listNode) {
        if (listNode == null) {
            return null;
        }
        ListNode head = listNode;
        ListNode head1 = listNode;
        int count = 0;
        while (listNode != null) {
            count++;
            listNode = listNode.next;
        }
        process(head1, 1, count);
        return head;
    }

    public static void process(ListNode listNodes, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        process(listNodes, left, mid);
        process(listNodes, mid + 1, right);
        mergeArr(listNodes, left, right);

    }

    public static void mergeArr(ListNode listNode, int left, int right) {
        ListNode head = listNode;
        ListNode leftNode = listNode;
        ListNode rightNode = null;
        ListNode oldNode = null;
        ListNode rightOldNode = null;
        int count = 0;
        while (head != null) {
            count++;
            if (count == left - 1) {
                oldNode = head;
                leftNode = head.next;
            }
            if (count == right) {
                rightNode = head;
                rightOldNode = head.next;
                break;
            }

            head = head.next;
        }
        ListNode loopLeft = leftNode;
        ListNode loopRight = rightNode;
        ListNode mergeNode = new ListNode(5);
        ListNode mergeCopy = mergeNode;
        while (loopLeft != null && loopRight != null) {
            mergeCopy = loopLeft.val > loopRight.val ? loopRight : loopLeft;
            loopLeft = loopLeft.next;
            loopRight = loopRight.next;
            if (loopLeft != null && loopRight != null) {
                mergeCopy = mergeCopy.next;
            }
        }
        if (null != oldNode) {
            oldNode.next = mergeNode.next;
        }
        mergeCopy.next = rightOldNode;

    }


}
